
//组合
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int kVal;
    int nVal;
    void dfs(int val)
    {
        if(path.size() == kVal)
        {
            ret.push_back(path);
            return;
        }
        if(val > nVal)
        {
            return;
        }  
        //如果选择val
        path.push_back(val);
        dfs(val+1);
        path.pop_back();
        //如果不选val
        dfs(val+1);
    }
    vector<vector<int>> combine(int n, int k) {
        kVal = k;
        nVal = n;
        dfs(1);
        return ret;
    }
};

//括号生成
class Solution {
public:
    vector<string> ret;
    string path;
    int nums[2] = {0, 0}; // 括号数量
    vector<string> dict = {"(",")"};
    void dfs(int n) {
        if (nums[0] == n && nums[1] == n) {
            ret.push_back(path);
            return;
        }
        // 如果选(
        if (nums[0] < n) {
            path.push_back('(');
            nums[0]++;
            dfs(n);
            // 恢复现场
            path.pop_back();
            nums[0]--;
        }
        // 如果选)
        if (nums[1] < nums[0]) {
            path.push_back(')');
            nums[1]++;
            dfs(n);
            // 恢复现场
            nums[1]--;
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n); 
        return ret;
    }
};

//全排列Ⅱ
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[10];
    void dfs(vector<int>& nums)
    {
        if(path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }
        //只关心“合法”的
        for(size_t i = 0 ; i < nums.size() ; ++i)
        {
            if(check[i] == false &&(i == 0 ||nums[i] != nums[i-1] || check[i-1] == true))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin() , nums.end());
        dfs(nums);
        return ret;
    }
};

//电话号码的字母组合
class Solution {
public:
    vector<string> dict = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> ret;
    string path;
    void dfs(string& digits , size_t pos)
    {
        if(path.size() == digits.size())
        {
            ret.push_back(path);
            return;
        }
        for(size_t i = 0 ; i < dict[digits[pos]-'0'].size() ; ++i)
        {
            path.push_back(dict[digits[pos]-'0'][i]);
            dfs(digits,pos+1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return{};
        dfs(digits,0);
        return ret;
    }
};

